package chapter1.section1;
/**
 * 三步反转：
 * 1. 将原字符串分为X和Y两部分，其中X为abc，Y为def
 * 2. 将X的所有字符串反转，即相当于反转abc为cba，再将Y的所有字符也反转，即相当于反转def得到fed
 * 3. 最后将上述步骤得到的结果整体反转，即反转cbafed为defabc，这样就完成了反转
 */
import org.junit.Test;

/*
 * 时间复杂度O(n),空间复杂度O(1)
 */
public class ReverseString {

	//反转字符串，from是反转的起点，to是终点
	public void reverseString(char[] s, int from, int to) {
		while(from < to) {
			char t = s[from];
			s[from++] = s[to];
			s[to--] = t;
		}
	}
	
	public void leftRotationString(char[] s, int n, int m) {
		//若要左移动大于n位，那么%n是等价的
		//n是字符串长度，m是要反转的前m个字符串，是一个分割节点
		//m %= n;   n是一个字符串的长度，而m是字符串的一个分割点，m必然小于n，所以m必然等于m%n，这个好像在这没啥用
		reverseString(s, 0, m-1);
		reverseString(s, m, n-1);
		reverseString(s, 0, n-1);
	}
	
	//测试方法
	@Test
	public void test() {
		String str = "abcdef";
		char[] s = str.toCharArray();
		leftRotationString(s,s.length,3);
		for(char c : s) {
			System.out.print(c+" ");
		}
	}
}
